1. Field of the Invention
The present invention relates to a improved adaptive binary arithmetic coder that provides improved processing speed and accuracy over conventional arithmetic coders.
2. Related Art
Arithmetic coders provide well-known algorithms for encoding data. Compression ratios of the arithmetic coders can reach the information theory limit. The arithmetic coder and decoder must possess good estimates of the probability distribution of each symbol to code. For each symbol to be coded in a string element, the encoder and decoder must possess a table containing estimated probabilities for the occurrence of each possible symbol at each point in the symbol string. The coders themselves must perform a table search and at least one multiplication. For this reason, arithmetic coders incur high computational expense. Binary adaptive arithmetic coders, such as the xe2x80x9cQ-Coder,xe2x80x9d by Pennebaker, et al. (1998) and the xe2x80x9cQM-Coder,xe2x80x9d by Ono (1993), have been developed to overcome this drawback.
A high-level system diagram of a prior art binary arithmetic coder is shown in FIG. 1. Data to be coded is input to an encoder 100. The encoder 100 encodes the data and outputs a string of coded data to a channel 200. A decoder 300 retrieves the code string from the channel 200 and replicates the original data by decoding the coded data.
The coding process often is described by the operation of the decoder 300. In the decoder, the code string is interpreted as a binary representation of a real number contained in the unit interval [0,1[. The binary arithmetic coder divides the unit interval into two sub-intervals having lengths that are proportional to the estimated probabilities of each value of the first bit in the symbol string. Any code string located in a first, lower sub-interval represents a symbol string starting with a zero (0). Conversely, any code string located in the upper sub-interval represents a symbol string starting with a one (1).
Each of the sub-intervals can be divided into two smaller sub-intervals having lengths that are proportional to the estimated conditional probabilities of the second symbol bit given the previously encoded symbol bit. Any code string located in one of these sub-intervals represents a symbol string starting with the corresponding two bit prefix.
The decoding process is repeated. Sub-intervals are themselves divided into smaller sub-intervals representing probabilities of the value of the next bit in the symbol string. The process produces a partition of the unit interval having sub-intervals that correspond to each possible value of the symbol string. Any code string in the interval can be chosen corresponding to the encoded symbol string.
According to theory, when an interval is divided into sub-intervals, the length of each sub-interval should be proportional to the probability of the value of the next data symbol to be decoded given the previous symbol bits. The probability distribution of the code string therefore would be uniform in the interval. Since each code bit is equally likely to be a 0 or a 1, it would carry as much information as information theory allows. In other words, the coder would achieve entropic compression.
The known Q-Coder and QM-Coder, while they represent advances over traditional arithmetic coders, do not provide performance that approaches entropic compression. Thus, there is a need in the art for a binary arithmetic coder that provides improved compression ratios than the Q-Code and the QM-Coder.
Decoding speed is an important performance characteristic of data coding systems. Decoding latency, the time that is required to generate decoded data once the coded data is received should be minimized wherever possible. Thus, decoders that introduce lengthy or complex computational processes to the decoding operation are disfavored. Accordingly, there is a need in the art for a data decoding scheme that is computationally simple and provides improved throughput of decoded data.
The present invention provides a binary arithmetic coder and decoder having important advantages over the prior art. The coding scheme provides improved coding accuracy over the prior art due to improved probability estimation and adaptation. It provides improved decoding speed through a xe2x80x9cfast pathxe2x80x9d design wherein decoding of a most probable symbol requires few computational steps.
According to the present invention, coded data represents data that is populated by more probable symbols (xe2x80x9cMPSxe2x80x9d) and less probable symbols (xe2x80x9cLPSxe2x80x9d). In an embodiment, the decoder receives a segment of the coded data as a binary fraction C. It defines a coding interval of possible values of C, the interval extending from a variable lower bound A to a constant upper bound 1. For each position in the decoded symbol string, the decoder computes a test value Z that subdivides the coding interval into sub-intervals according to the relative probabilities that an MPS or an LPS occurs in the position. A first sub-interval extends from the lower bound A to the test value Z; the second sub-interval extending from the test value Z to 1. If C is greater than Z, the decoder emits an MPS for the current position in the decoded symbol string and sets the lower bound A to the test variable Z for use during decoding of the next position in the decoded symbol string. If C is less than Z, the decoder emits an LPS and computes a new lower bound A and a new binary fraction C for use during decoding of the next position in the decoded symbol string. The encoder operates according to analogous techniques to compose coded data from original data.